package org.liaohailong.victor;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/11/22 10:25
 * Describe:
 */
public class StackStudy {
    Map<String, Integer> priority = new HashMap<>();

    public StackStudy() {
        priority.put("+", 1);
        priority.put("-", 1);
        priority.put("*", 2);
        priority.put("/", 2);
        priority.put("(", 0);
        priority.put(")", 3);
    }

    /**
     * 1，都是正整数
     * 2，运算得出结果
     *
     * @param token 3*(2*1+3+0)/5+1
     */
    public int calc(String token) {
        /*
         * 1，去括号，括号内公式先算出结果（使用栈结构处理）
         * 2，计算优先级，乘除先算，加减后算（使用栈结构处理）
         * */
        LinkedList<Integer> valStack = new LinkedList<>();
        LinkedList<String> opStack = new LinkedList<>();
        char[] arr = token.toCharArray();
        for (char c : arr) {
            String val = String.valueOf(c);
            // 判断是否为操作符号
            boolean isOp = priority.containsKey(val);
            if (isOp) {
                if (val.equals("(")) {
                    // 左括号先入栈，等待右括号出现，再计算
                    opStack.push(val);
                } else if (val.equals(")")) {
                    // 右括号出现，开始计算，直到出现第一个左括号
                    // 截取出括号内的运算
                    StringBuilder sb = new StringBuilder();
                    sb.append(valStack.pop());
                    while (true) {
                        String lastOp = opStack.peek();
                        if ("(".equals(lastOp)) break;
                        sb.insert(0, opStack.pop()).insert(0, valStack.pop());
                    }
                    // 弹出(
                    opStack.pop();
                    // 3*(2*1+3+0)/5+1 取出 2*1+3+0
                    String simple = sb.toString(); // 无括号的运算
                    int result = calcSimple(simple);
                    valStack.push(result); // 值压入栈顶，作为下一个运算符的第二个参数值
                    // 3*5/5+1
                } else {
                    // + - * / 入栈
                    opStack.push(val);
                }
            } else {
                valStack.push(Integer.parseInt(val));
            }
        }

        // 去括号处理完毕之后，还剩下一段运算：
        // 3*(2*1+3+0)/5 + 1 -> 3*5/5 +1
        StringBuilder sb = new StringBuilder();
        sb.append(valStack.pop());
        while (true) {
            String lastOp = opStack.peek();
            if (null == lastOp) break;
            sb.insert(0, opStack.pop()).insert(0, valStack.pop());
        }
        String simple = sb.toString(); // 无括号的运算

        return calcSimple(simple);
    }

    /**
     * @param token 2*1+3+0
     */
    public int calcSimple(String token) {
        /*
         * 先把乘除运算处理好，剩下再处理加减运算
         * */
        LinkedList<Integer> valStack = new LinkedList<>();
        LinkedList<String> opStack = new LinkedList<>();

        // 以下while循环把所有的乘数运算处理完毕，并且把加减运算记录到stack中
        int pos = 0;
        char[] arr = token.toCharArray();
        while (pos < arr.length) {
            char curr = arr[pos];

            String val = String.valueOf(curr);
            boolean isOp = priority.containsKey(val);
            if (isOp) {
                int p = priority.get(val);
                if (p >= 2) {
                    // 遇到乘除
                    pos++;
                    int nextVal = Character.digit(arr[pos], 10);
                    int lastVal = valStack.pop();
                    int resultVal = doOp(lastVal, nextVal, val);
                    valStack.push(resultVal);
                } else {
                    // 遇到加减
                    opStack.push(val);
                }
            } else {
                valStack.push(Integer.parseInt(val));
            }

            pos++;
        }

        // 计算加减运算
        while (!opStack.isEmpty()) {
            String op = opStack.pop();
            int nextVal = valStack.pop();
            int lastVal = valStack.pop();
            int resultVal = doOp(lastVal, nextVal, op);
            valStack.push(resultVal);
        }

        return valStack.pop();
    }

    private int doOp(int val1, int val2, String op) {
        int result = 0;
        switch (op) {
            case "+":
                result = val1 + val2;
                break;
            case "-":
                result = val1 - val2;
                break;
            case "*":
                result = val1 * val2;
                break;
            case "/":
                result = val1 / val2;
                break;
        }
        return result;
    }
}
